#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef struct node
{
	int data;
	struct node *lchild;
	struct node *rchild;
	struct node *parent;
}node, *pnode;

pnode construct_node(int data)
{
	printf("%d\n", data);
	pnode temp = (pnode)malloc(sizeof(node));
	memset(temp, 0, sizeof(node));
	temp->data = data;
	temp->lchild = temp->rchild = temp->parent = NULL;
	return temp;
}

pnode add_node(pnode root, pnode newnode)
{
	if(root == NULL)
	{
		root = newnode;
		return root;
	}

	pnode temp = root;
	while(temp != NULL)
	{
		if(temp->data > newnode->data)
		{
			if(temp->lchild == NULL)
			{
				temp->lchild = newnode;
				newnode->parent = temp;
				return root;
			}
			else
				temp = temp->lchild;
		}
		else if(temp->data < newnode->data)
		{
			if(temp->rchild == NULL)
			{
				temp->rchild = newnode;
				newnode->parent = temp;
				return root;
			}
			else
				temp = temp->rchild;
		}
		else
			return root;
	}
}

void preorder_traversal(pnode root)
{
	if(root == NULL)
		return;

	pnode temp = root;
	if(temp != NULL)
	{
		printf("%d \t ", temp->data);
		if(temp->lchild != NULL)
		{
			preorder_traversal(temp->lchild);
		}
		if(temp->rchild != NULL)
		{
			preorder_traversal(temp->rchild);
		}
	}
}

void inorder_traversal(pnode root)
{
	if(root == NULL)
		return;

	pnode temp = root;
	if(temp != NULL)
	{
		if(temp->lchild != NULL)
		{
			inorder_traversal(temp->lchild);
		}
		printf("%d \t ", temp->data);
		if(temp->rchild != NULL)
		{
			inorder_traversal(temp->rchild);
		}
	}
}

void postorder_traversal(pnode root)
{
	if(root == NULL)
		return;

	pnode temp = root;
	if(temp != NULL)
	{
		if(temp->lchild != NULL)
		{
			postorder_traversal(temp->lchild);
		}
		if(temp->rchild != NULL)
		{
			postorder_traversal(temp->rchild);
		}
		printf("%d \t ", temp->data);
	}
}

pnode search_tree(pnode root, int data)
{
	pnode temp = root;

	while(temp != NULL)
	{
		if(temp->data == data)
		{
			return temp;
		}
		else if(temp->data < data)
		{
			temp = temp->rchild;
		}
		else
		{
			temp = temp->lchild;
		}
	}

	return NULL;
}

pnode max_left_tree(pnode root)
{
	assert(root);
	pnode temp = root;
	while(temp != NULL && root->rchild != NULL)
	{
		temp = temp->rchild;
	}

	return temp;
}

void cut_link_from_tree(pnode node)
{
	if(node->lchild == NULL && node->rchild == NULL)
	{
		if(node->parent->lchild == node)
			node->parent->lchild = NULL;
		else if(node->parent->rchild == node)
			node->parent->rchild = NULL:
	}
	else
	{
		if(node->lchild != NULL)
		{
			if(node->parent->lchild == node)
				node->parent->lchild = node->lchild;
			else if(node->parent->rchild == node)
				node->parent->rchild = node->rchild;
		}
		else if(node->rchild != NULL)
		{
			if(node->parent->lchild == node)
				node->parent->lchild = node->rchild;
			else if(node->parent->rchild == node)
				node->parent->rchild = node->rchild;
		}
	}
}

pnode del_tree(pnode root, int data)
{
	pnode res = search_tree(root, data);
	if(res == NULL)
	{
		printf("not has this data\n");
		return root;
	}

	if(res->lchild != NULL)
	{
		pnode replace = max_left_tree(res);
	}
	else if(res->rchild != NULL)
	{
		pnode replace = min_right_tree(res);
	}
	else
	{
		cut_link_from_tree(res);
		free(res);
		if(res == root)
			return NULL;
		else
			return root;
	}

	cut_link_from_tree(replace);
	res->data = replace->data;
	free(replace);
}

int main(int argc, char *argv[])
{
	if(argc != 2)
	{
		printf("pls usage %s data_count\n", argv[0]);
		exit(EXIT_FAILURE);
	}

	int num = atoi(argv[1]);
	srand(time(NULL));

	pnode root = NULL;
	int i;
	for(i=0; i<num; i++)
	{
		pnode temp = construct_node(rand()%500);
		root = add_node(root, temp);
	}

	printf("----- preorder traversal -----\n");
	preorder_traversal(root);
	printf("\n");
	printf("----- inorder traversal -----\n");
	inorder_traversal(root);
	printf("\n");
	printf("----- postorder traversal -----\n");
	postorder_traversal(root);
	printf("\n");

	return 0;
}
